#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/// Definition for an interval.
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

bool compare(const Interval &a, const Interval &b){

    if(a.end != b.end)
        return a.end < b.end;		// 谁结束早谁排在前面
    return a.start < b.start;		// 谁起始值靠前，谁排在前面
}

// 435: Non-overlapping Intervals  : 最少要删除多少个组合 【参考递增子序列】
// 时间复杂度: O(n^2) 空间复杂度: O(n)

class Solution {
public:
    int eraseOverlapIntervals(vector<Interval>& intervals) {
  		if(intervals.size() == 0){
			return 0;
		}  
		
		sort(intervals.begin(), intervals.end(), compare);

		int res = 1;	// 结尾最早的元素排在第0位，肯定取这个位置
		int pre = 0;	// 遍历i时之前使用的区间
		for(int i = 1;i < intervals.size(); i++){
			// 选择当前区间i， 同时之前区间索引变为i
			if(intervals[i].start >= intervals[pre].end){
				res++;
				pre = i;
			}
		}
		
		return intervals.size() - res;
    }
};

int main(){
	Interval interval1[] = {Interval(1,2), Interval(2,3), Interval(3,4), Interval(1,3)};
    vector<Interval> v1(interval1, interval1 + sizeof(interval1)/sizeof(Interval));
    cout << Solution().eraseOverlapIntervals(v1) << endl;

    Interval interval2[] = {Interval(1,2), Interval(1,2), Interval(1,2)};
    vector<Interval> v2(interval2, interval2 + sizeof(interval2)/sizeof(Interval));
    cout << Solution().eraseOverlapIntervals(v2) << endl;

    Interval interval3[] = {Interval(1,2), Interval(2,3)};
    vector<Interval> v3(interval3, interval3 + sizeof(interval3)/sizeof(Interval));
    cout << Solution().eraseOverlapIntervals(v3) << endl;

    return 0;
}
